// 给定一个未排序的整数数组，找出最长连续序列的长度。

// 要求算法的时间复杂度为 O(n)。

// 示例:

// 输入: [100, 4, 200, 1, 3, 2]
// 输出: 4
// 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::unordered_set;
using std::unordered_map;
using std::max;

// 使用set
// 空间换时间
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> set(nums.begin(), nums.end());
        for (int& num : nums) {
            if (!set.count(num)) continue; // 如果集合中这个数字已经被删掉，就跳过
            set.erase(num); // 删掉集合中当前的num
            int pre = num - 1; // 前一个数
            int next = num + 1; // 后一个数
            while (set.count(pre)) set.erase(pre--); // 把集合中前面的连续的数字都删掉
            while (set.count(next)) set.erase(next++); // 把集合中后面的连续的数字都删掉
            res = max(res, next - pre - 1);
        }
        return res;
    }
};

// 哈希表
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_map<int, int> hash{};
        for (int& num : nums) {
            if (hash.count(num)) continue; // 如果哈希表中有这个数字相关的结果，就跳过
            int left = hash.count(num - 1) ? hash[num-1] : 0; // 左边长度
            int right = hash.count(num + 1) ? hash[num + 1] : 0; // 右边长度
            int sum = left + right + 1; // 总长度需要加上自身也就是加1
            hash[num] = sum;
            res = max(res, sum);
            // 更新两端的哈希表，至于中间的某些数字可以跳过
            hash[num - left] = sum;
            hash[num + right] = sum;
        }
        return res;
    }      
};

/* 哈希表
遍历每一个数，找其后面的数
判断当前数字的前一个数是否存在，存在就跳过当前的数字
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> nums_set{};
        for (const int& num : nums) { // 去重
            nums_set.insert(num);
        }
        int res{0};
        for (const int& num : nums_set) {
            if (nums_set.count(num - 1) == 0) { // 找不到前一个数
                int curNum{num};
                int curLength{1};
                while (nums_set.count(curNum + 1) != 0) {
                    curNum += 1;
                    curLength += 1;
                }
                if (curLength > res) res = curLength;
            }
        }
        return res;
    }
};